package com.jhy.review.day03;

import com.jhy.review.day01.Node;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 二叉树的序列化和反序列化
 * 就是内存里的一棵树如何变成字符串形式，又如何从字符串形式变成内存里的树
 * 2022年7月23日15:54:26
 */


public class SerializationAndDeserialization {
    // 序列化 先序遍历实现序列化的结果
    public static String serialization(Node head){
        if(head == null){
            return "#_";
        }
        String res = head.value + "_";
        return res +  serialization(head.left) + serialization(head.right);
    }
    // 反序列化
    public static Node deserialization(){
        Node node = new Node();
        // 序列化之前的结果
        String res = serialization(node);
        // 现在进行反序列化
        String[] list = res.split("_");
        // 用队列来存放这个数组
        Queue<String> queue = new LinkedList<>();
        for (int i = 0; i < list.length; i++) {
            queue.add(list[i]);
        }
        // 下面调用方法将队列的里面的值转化为树
        return process(queue);
    }
    // 调用方法
    public static  Node process(Queue<String> queue){
        String value = queue.poll();
        // base case
        if(value.equals("#")){
            return null;
        }
        // 声明头节点
        Node node = new Node(Integer.valueOf(value));
        // 定义左边
        node.left = process(queue);
        // 定义右边
        node.right = process(queue);
        return node;
    }
    

}
